package sort;

import java.util.Arrays;

/**
 * @author : niu niu
 * @version : 1.0.0
 * @date : 2022/11/15 13:36
 */
public class MergeSortPlus {
    public static void mergeSort2(long[] array) {
        long[] e = new long[array.length];
        mergeSortInternal2(array, 0, array.length, e);
    }

    private static void mergeSortInternal2(long[] array, int from, int to, long[] e) {
        if (to <= 1 + from) {
            return;
        }

        // 把待排序区间对半分开
        // 找到中间位置下标
        int mid = from + (to - from) / 2;
        // 整个区间被切割成
        // [from, mid)
        // [mid, to)
        // 按照相同的方式，先把左右两个区间变得有序
        mergeSortInternal2(array, from, mid, e);
        mergeSortInternal2(array, mid, to, e);

        // [from, mid)   有序了
        // [mid, to)     有序了

        merge2(array, from, mid, to, e);
    }

    private static void merge2(long[] array, int from, int mid, int to, long[] e) {
        int size = to - from;
        int eIdx = 0;

        int leftIdx = from; // 左边区间要处理的元素的下标
        int rightIdx = mid; // 右边区间要处理的元素的下标
        // 什么条件表示左边区间 [from, mid) 就没有元素了   leftIdx == mid
        // 同理右边区间：rightIdx == to
        // 两个区间都有元素的时候才要比较
        // 左区间有元素：leftIdx < mid
        // 右: rightIdx < to
        // leftIdx < mid && rightIdx < to
        while (leftIdx < mid && rightIdx < to) {
            // 要比较的两个元素 array[leftIdx] 和 array[rightIdx]
            if (array[leftIdx] <= array[rightIdx]) {
                // 取左边的元素放入 e 数组
                e[eIdx] = array[leftIdx];
                eIdx++;
                leftIdx++;
            } else {
                // 取右边的元素放入 e 数组
                e[eIdx] = array[rightIdx];
                eIdx++;
                rightIdx++;
            }
        }
    }
    public static void main(String[] args) {
        long[] array = { 9, 5, 1, 7, 2, 8, 3, 6, 0, 4 };

        System.out.println(Arrays.toString(array));
//        long[] array = {1, 2, 3};
//        Arrays.sort(array);     // 基本类型使用快排
//
//        Integer[] a = { 1, 2, 3 };
//        Arrays.sort(a);         // 引用类型用了归并
    }
}
